113. 路径总和 II

Similar Question

leading to the advanced question

Solution Tips

方案一: DFS

前序遍历，直到叶节点

var pathSum = function (root, sum) {
    if (root === null) return 0
    const res = []
    dfs(root, sum)
    return res
    function dfs(node, sum, path = []) {
        if (node === null) return
        path.push(node.val)
        // 保证是叶节点
        if (sum === node.val && node.left == null && node.right == null) res.push([...path])
        dfs(node.left, sum - node.val, path)
        dfs(node.right, sum - node.val, path)
        path.pop()
    }
}

console.log(pathSum(bst.root(), 1))

方案二: BFS

用栈代替递归调用栈，参考 I